/**
* Created with CLion.
* User:Lenovo
* Date:2023-06-03
* Time:1:50
* Description:
*/

#include "BinaryTree.h"

void BinaryTreeTest1()
{
    BTNode *root = CreateBinaryTree();

    PrevOrder(root);
    printf("\n");

    InOrder(root);
    printf("\n");

    PostOrder(root);
    printf("\n");

    int size = BTreeSize(root);
    printf("size = %d\n", size);

    int leafSize = BTreeLeafSize(root);
    printf("leafSize = %d\n", leafSize);

    int height = BTreeHeight(root);
    printf("h = %d\n", height);

    int k3 = BTreeLevelKSize(root, 3);
    printf("k3 = %d\n", k3);

    int k4 = BTreeLevelKSize(root, 4);
    printf("k4 = %d\n", k4);

    LevelOrder(root);

    BTNode *ret = BTreeFind(root, 5);
    assert(ret);
    ret -> data = 8;
    PrevOrder(root);
    printf("\n");

    if (BTreeComplete(root))
    {
        printf("true\n");
    }
    else
    {
        printf("false\n");
    }

    printf("\n");
}

int main()
{
    // 链式二叉树的增删查改没有意义，因为不需要用这样一个复杂的结构存储数据，一般用更复杂的 AVL 树来进行增删查改
    // 但是学习控制递归结构是有价值的，为后续学习打基础
    // 很多 OJ 题就是这个地方的
    // 不学增删查改，主要掌握递归结构

    // 二叉树的 4 种遍历方式：
    // 前序遍历：根 -> 左子树 -> 右子树 (根在前面)
    // 中序遍历：左子树 -> 根 -> 右子树 (根在中间)
    // 后序遍历：左子树 -> 右子树 -> 根 (根在后面)
    // 层序遍历：一层一层访问

    //      1
    //     / \
    //    2   4
    //   /   / \
    //  3   5   6
    //     /
    //    7

    // (N 代表空树访问)
    // 前序遍历：1 -> 2 -> 3 -> N -> N -> N -> 4 -> 5 -> 7 -> N -> N -> N -> 6 -> N -> N
    //         1 -> 2 -> 3 -> 4 -> 5 -> 7 -> 6
    // 中序遍历：N -> 3 -> N -> 2 -> N -> 1 -> N -> 7 -> N -> 5 -> N -> 4 -> N -> 6 -> N
    //         3 -> 2 -> 1 -> 7 -> 5 -> 4 -> 6
    // 后序遍历：N -> N -> 3 -> N -> 2 -> N -> N -> 7 -> N -> 5 -> N -> N -> 6 -> 4 -> 1
    //         3 -> 2 -> 7 -> 5 -> 6 -> 4 -> 1
    // 遍历算法的时间复杂度：O(N)  空间复杂度：O(h) (logN <= h <= N)

    BinaryTreeTest1();

    // 单值二叉树：树里面所有的值都一样
    // 层序遍历：1 -> 2 -> 4 -> 3 -> N -> 5 -> 6 -> N -> N -> 7 -> N -> N -> N -> N -> N
    //         1 -> 2 -> 4 -> 3 -> 5 -> 6 -> 7
    // 使用队列：上一层出的时候带下一层进

    return 0;
}

